# -*- coding: utf-8 -*-

''' 
Autores: 
Pedro Godinho - 6355
Pedro Lopes - 9850
'''

from random import uniform
from time import clock
import matplotlib.pyplot as plt

''' Class responsable for InsertionSort algorithm and tests'''
class InsertionSort:

    '''@param A: list to sort'''
    def insertion_sort(self, A):
            for j in range(1,len(A)):
                    key = A[j]
                    i = j - 1
                    while i > -1 and A[i] > key:
                            A[i+1] = A[i]
                            i = i - 1
                    A[i + 1] = key
                    pass
            pass
    pass

    def grafico(self):
        Z = [1] + range(50, 1050, 50)
        T = []
        M = 25
        for n in Z:
            A = [ uniform(0.0,1.0) for k in xrange(n)]
            tempos = []
            for k in range(M):
                t1 = clock()
                self.insertion_sort(A)
                t2 = clock()
                tempos.append(t2-t1)
            media = reduce(lambda x, y: x + y, tempos) / len(tempos)
            var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)
        
            T.append((n,media, var))

        X = [n for n, media, var in T]
        Y = [media for n, media, var in T]
        ct=252e6
        Z = [(n**2)/ct for n, media, var in T]


        plt.grid(True)
        plt.ylabel(u'T(n) - tempo de execução médio em segundos')
        plt.xlabel(u'n - número de elementos')
        plt.plot(X,Y,'rs', label="resultado experimental")
        plt.plot(X, Z, 'b^', label=u"previsão teórica")
        plt.title("Insertion Sort")
        plt.legend()
        plt.show()
